package lc_416_分割等和子集;

import java.util.Arrays;

public class Solution {
    public boolean canPartition(int[] nums) {
        int tot = Arrays.stream(nums).sum();
        if ((tot & 1) == 1)
            return false;
        tot >>= 1;
        boolean[] dp = new boolean[tot + 1];
        dp[0] = true;
        for (int i = 0; i < nums.length; i++) {
            for (int j = tot; j >= 0; j--) {
                if (dp[j] && j + nums[i] <= tot) {
                    dp[j + nums[i]] = true;
                }
            }
        }
        return dp[tot];
    }
}